<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      let count = 0;
      const arr = [5, 3, 8, 6, 4];
      function mergeSort(arr) {
        if (arr.length <= 1) {
          return arr;
        }
        const mid = Math.floor(arr.length / 2);
        const leftArr = arr.slice(0, mid);
        const rightArr = arr.slice(mid);
        return merge(mergeSort(leftArr), mergeSort(rightArr));
      }

      function merge(leftArr, rightArr) {
        let i = 0;
        let j = 0;
        const result = [];
        while (i < leftArr.length && j < rightArr.length) {
          if (leftArr[i] < rightArr[j]) {
            result.push(leftArr[i]);
            i++;
          } else {
            result.push(rightArr[j]);
            j++;
          }
        }
        while (i < leftArr.length) {
          result.push(leftArr[i]);
          i++;
        }
        while (j < rightArr.length) {
          result.push(rightArr[j]);
          j++;
        }
        return result;
      }

      // 示例
      console.log(mergeSort(arr), `运行了${count}次`); // [3, 4, 5, 6, 8] 运行了15次

      // let arr = [4, 4, 6, 5, 3, 2, 8, 1];
      // console.log(arr.toString());

      // quickSort(arr, 0, arr.length - 1);
      // console.log(arr.toString());

      // function quickSort(arr, startIndex, endIndex) {
      //   // // 递归结束条件:startIndex大于或等于endIndex时
      //   if (startIndex >= endIndex) return;

      //   // 得到基准元素位置
      //   let pivotIndex = partition(arr, startIndex, endIndex);

      //   // 根据基准元素，分成两部分进行递归排序
      //   quickSort(arr, startIndex, pivotIndex - 1);
      //   quickSort(arr, pivotIndex + 1, endIndex);
      // }

      // function partition(arr, startIndex, endIndex) {
      //   // 取第1个位置(也可以选择随机位置)的元素作为基准元素
      //   let pivot = arr[startIndex];
      //   let left = startIndex;
      //   let right = endIndex;

      //   while (left != right) {
      //     //控制right 指针比较并左移
      //     while (left < right && arr[right] > pivot) {
      //       right--;
      //     }
      //     //控制left 指针比较并右移
      //     while (left < right && arr[left] <= pivot) {
      //       left++;
      //     }

      //     // 交换left 和right指针所指向的元素
      //     if (left < right) {
      //       let p = arr[left];
      //       arr[left] = arr[right];
      //       arr[right] = p;
      //     }
      //   }
      //   // pivot 和指针重合点交换。
      //   arr[startIndex] = arr[left];
      //   arr[left] = arr[pivot];

      //   return left;
      // }
    </script>
  </body>
</html>
